﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>


//给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
//找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
//时间复杂度O(n);!!!

//int maxArea(int* height, int heightSize) {
//    int max = 0;
//    if (heightSize == 0 && heightSize == 1)
//    {
//        return max;
//    }
//    int left = 0;
//    int right = heightSize - 1;
//    while (left < right)
//    {
//        int width = right - left;
//        if (height[left] < height[right])
//        {
//            if (height[left] * width > max)
//            {
//                max = height[left] * width;
//            }
//            left++;
//        }
//        else if (height[left] > height[right])
//        {
//            if (height[right] * width > max)
//            {
//                max = height[right] * width;
//            }
//            right--;
//        }
//        else if (height[left + 1] > height[right])
//        {
//            if (height[right] * width > max)
//            {
//                max = height[right] * width;
//            }
//            left++;
//        }
//        else if (height[left] > height[right - 1])
//        {
//            if (height[right] * width > max)
//            {
//                max = height[right] * width;
//            }
//            right--;
//        }
//        else
//        {
//            if (height[right] * width > max)
//            {
//                max = height[right] * width;
//            }
//            left++;
//            right--;
//        }
//    }
//    return max;
//}

//罗马数字反转
// 暴力求解
//int romanToInt(char* s) {
//    int max = 0;
//    if (s == NULL)
//    {
//        return max;
//    }
//    int sz = strlen(s);
//    int i = 0;
//    while (i < sz)
//    {
//        if (*(s + i) == 'M')
//        {
//            max += 1000;
//            i++;
//        }
//        else if (*(s + i) == 'D')
//        {
//            max += 500;
//            i++;
//        }
//        else if (*(s + i) == 'C')
//        {
//            if (*(s + i + 1) == 'M')
//            {
//                max += 900;
//                i += 2;
//            }
//            else if (*(s + i + 1) == 'D')
//            {
//                max += 400;
//                i += 2;
//            }
//            else
//            {
//                max += 100;
//                i++;
//            }
//        }
//        else if (*(s + i) == 'L')
//        {
//            max += 50;
//            i++;
//        }
//        else if (*(s + i) == 'X')
//        {
//            if (*(s + i + 1) == 'C')
//            {
//                max += 90;
//                i += 2;
//            }
//            else if (*(s + i + 1) == 'L')
//            {
//                max += 40;
//                i += 2;
//            }
//            else
//            {
//                max += 10;
//                i++;
//            }
//        }
//        else if (*(s + i) == 'V')
//        {
//            max += 5;
//            i++;
//        }
//        else if (*(s + i) == 'I')
//        {
//            if (*(s + i + 1) == 'X')
//            {
//                max += 9;
//                i += 2;
//            }
//            else if (*(s + i + 1) == 'V')
//            {
//                max += 4;
//                i += 2;
//            }
//            else
//            {
//                max += 1;
//                i++;
//            }
//        }
//    }
//    return max;
//}
//巧妙解法
//int romanToInt(char* s)
//{
//	if (s == NULL)
//	{
//		return 0;
//	}
//	int i = 0;
//	int num = 0;
//	int sz = strlen(s);
//	int demax = 1000;
//	int z = 0;
//	for (i = 0; i < sz; i++)
//	{
//		switch (s[i])
//		{
//		case 'M':
//			z = 1000;
//			break;
//		case 'D':
//			z = 500;
//			break;
//		case 'C':
//			z = 100;
//			break;
//		case 'L':
//			z = 50;
//			break;
//		case 'X':
//			z = 10;
//			break;
//		case 'V':
//			z = 5;
//			break;
//		case 'I':
//			z = 1;
//			break;
//		}
//		if (z > demax)
//		{
//			num -= 2*demax;
//			num += z;
//		}
//		else
//		{
//			num += z;
//		}
//		demax = z;
//	}
//	return num;
//}

char* longestCommonPrefix(char** strs, int strsSize) {
    int p1 = 0;
    int p2 = 0;
    int i = strlen(strs[0]);
    char* sp = (char*)malloc(sizeof(char) * (i + 1));
    strncpy(sp, strs[0], (i + 1));
    for (i = 1; i < strsSize; i++)
    {
        while (strs[i][p1] != 0 && sp[p2] != 0)
        {
            if (strs[i][p1] == sp[p2])
            {
                p1++;
                p2++;
            }
            else
            {
                break;
            }
        }
        if (p1 == 0)
        {
            return NULL;
        }
        else
        {
            free(sp);
            sp = (char*)malloc(sizeof(char) * (p2 + 1));
            strncpy(sp, strs[i], (p2 ));
            sp[p2 + 1] = '\0';
        }
    }
    return sp;
}

